public class Solution1032 {

    public static class Trie{
        boolean end;
        Trie[] children=new Trie[26];

        public void insert(String s){
            Trie node=this;
            for (char c : s.toCharArray()) {
                if (node.children[c-'a']==null){
                    node.children[c-'a']=new Trie();
                }
                node=node.children[c-'a'];
            }
            node.end=true;
        }

        public boolean query(StringBuilder stringBuilder){
            Trie node=this;
            for (int i=stringBuilder.length()-1;i>=0;i--){
                if (node.children[stringBuilder.charAt(i)-'a']==null){
                    return false;
                }
                node=node.children[stringBuilder.charAt(i)-'a'];
                if (node.end){
                    return true;
                }
            }
            return false;
        }
    }

    Trie trie=new Trie();
    StringBuilder stringBuilder=new StringBuilder();

    public Solution1032(String[] words) {
        for (String word : words) {
            trie.insert(new StringBuilder(word).reverse().toString());
        }
    }

    public boolean query(char letter) {
        stringBuilder.append(letter);
        return trie.query(stringBuilder);
    }

    public static void main(String[] args) {
        Solution1032 solution1032=new Solution1032(new String[]{"cd", "f", "kl"});
        System.out.println(solution1032.query('a'));
        System.out.println(solution1032.query('b'));
        System.out.println(solution1032.query('c'));
        System.out.println(solution1032.query('d'));
        System.out.println(solution1032.query('e'));
        System.out.println(solution1032.query('f'));
        System.out.println(solution1032.query('g'));
        System.out.println(solution1032.query('h'));
        System.out.println(solution1032.query('i'));
        System.out.println(solution1032.query('j'));
        System.out.println(solution1032.query('k'));
        System.out.println(solution1032.query('l'));
    }
}
